package newBee.class1;

import common.ArrayStack;
import common.ArrayUtils;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.cn/problems/next-greater-element-i/?envType=problem-list-v2&envId=monotonic-stack
 * 下一个更大元素
 * <p>
 * 解题思路：
 * 小 压 大 ：小的在上面，大的在下面，每次出栈的都是最近较大值
 * 1,3,4,2
 */
public class Code02_nextGreaterElement {
    public static void main(String[] args) {
        int[] nums1 = {4, 2, 8};
        int[] nums2 = {3, 8, 2, 4, 1, 6, 5, 9, 7, 11};
        int[] res = nextGreaterElement(nums1, nums2);
        ArrayUtils.printArr(res);
    }

    public static int[] nextGreaterElement(int[] nums1, int[] arr) {
        ArrayStack stack = new ArrayStack(arr.length);
        int[] ans = new int[nums1.length];
        int[] x = new int[arr.length];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            // 栈顶 > arr[i]
            while (!stack.isEmpty() && arr[stack.peek()] <= arr[i]) {
                int k = stack.pop();
                map.put(arr[k], arr[i]);
                x[k] = i;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int k = stack.pop();
            map.put(arr[k], -1);
            x[k] = -1;
        }
        for (int i = 0; i < nums1.length; i++) {
            ans[i] = map.get(nums1[i]);
        }
        ArrayUtils.printArr(x);
        return ans;
    }
}
